package interview;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class interview_08_09 {
    public List<String> generateParenthesis(int n) {
        List<String> result=new LinkedList<>();
        Stack<Integer> stack=new Stack<>();
        search(result,new StringBuilder(),n,n,stack);
        return result;
    }
    public void search(List<String> result,StringBuilder stringBuilder,int left,int right,Stack<Integer> stack){
        if(stack.isEmpty()&&left==0&&right==0){
            result.add(stringBuilder.toString());
            return;
        }
        if(left!=0){
            stringBuilder.append("(");
            stack.push(0);
            search(result, stringBuilder, left-1, right, stack);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
            stack.pop();
        }
        if(right!=0){
            stringBuilder.append(")");
            boolean flag=false;
            if(!stack.isEmpty()&&stack.peek()==0){
                flag=true;
                stack.pop();
            }
            else{
                stack.push(1);
            }
            search(result, stringBuilder, left, right-1, stack);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
            if(flag){
                stack.push(0);
            }else{
                stack.pop();
            }
        }
    }
}
